package top.humbleyuan.double_pointer;

import top.humbleyuan.datastructure.linkedlist.IntersectLinkedList;
import top.humbleyuan.datastructure.linkedlist.LinkNode;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 22:33
 * @Des 相交链表
 */
public class LeetCode_160 {
    /**
     * 相交链表
     * 双指针：从两个指针头开始，遍历完当前链表开始遍历第二个，会在相交点相遇
     */
    public static void main(String[] args) {
        /**
         * 生成相交链表
         */
        LinkNode firstHead = new LinkNode(2);
        int[] vals1 = {4, 3, 7, 8, 5, 6, 4};
        firstHead = LinkNode.formLink(firstHead, vals1);

        LinkNode secondHead = new LinkNode(7);
        int[] vals2 = {9, 8, 5, 6, 4};
        secondHead = LinkNode.formLink(secondHead, vals2);

        IntersectLinkedList intersectLinkedList =
                new IntersectLinkedList(firstHead, secondHead, 4, 2);

        firstHead = intersectLinkedList.getFirstHead();
        secondHead = intersectLinkedList.getSecondHead();

        int firstCycleIndex = 1,
                secondCycleIndex = 1;

        LinkNode firstTemp = firstHead;
        LinkNode secondTemp = secondHead;

        LinkNode firstEnd = null;
        LinkNode secondEnd = null;
        while (firstCycleIndex <= 2 && secondCycleIndex <= 2) {

            if((firstEnd != null && secondEnd != null) && firstEnd != secondEnd) {
                System.out.println("不相交");
                return;
            }
            if(firstTemp == secondTemp) {
                System.out.println("相交点:" + firstTemp.val);
                return;
            }

            if(firstTemp.next == null && firstCycleIndex <= 2) {
                firstEnd = firstTemp;
                firstTemp = secondHead;
                firstCycleIndex ++;
            }else {
                firstTemp = firstTemp.next;
            }

            if(secondTemp.next == null && secondCycleIndex <= 2) {
                secondEnd = secondTemp;
                secondTemp = firstHead;
                secondCycleIndex ++;
            }else {
                secondTemp = secondTemp.next;
            }

        }
    }
}
